/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DickYang
 * Date: 2023-07-10
 * Time: 8:29
 *
 * 以双向链表模拟实现双端队列(deque)
 */
public class MyDeque {
    static class Node {
        int val;
        Node prev;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    private Node head; //队头
    private Node last; //队尾
    private int usedSize;

    //入队,向双向链表尾部位置插入新节点
    public void lastOffer(int e) {
        Node node = new Node(e);
        if (head == null) { // 第一次插入
            head = node;
        }else {
            //不是第一次插入
            last.next = node;
            last.next.prev = last;
        }
        last = node;
        usedSize++;
    }
    //入队,向双向链表头部位置插入新节点
    public void headOffer(int e) {
        Node node = new Node(e);
        if (head == null) { // 第一次插入
            head = node;
            last = node;
        } else {
            //不是第一次插入
            node.next = head;
            head.prev = node;
            head = node;
        }
        usedSize++;
    }

    //出队列,将双向链表尾部第一个节点删除掉
    public int lastPoll() {
        if(isEmpty()) {
            throw new NullPointerException("链表无数据!");
        }
        int val = last.val;
        if (head == last) {
            head = null;
            last = null;
        }else {
            last = last.prev;
            last.next = null;
        }
        usedSize--;
        return val;
    }
    //出队列,将双向链表头部第一个节点删除掉
    public int headPoll() {
        if(isEmpty()) {
            throw new NullPointerException("链表无数据!");
        }
        int val = head.val;
        if (head == last) { //只有一个节点
            head = null;
            last = null;
        } else {
            head = head.next;
            head.prev.next = null;
            head.prev = null;
        }
        usedSize--;
        return val;
    }

    //获取队头元素,获取链表中第一个节点的值
    public int headPeek(){
        if (isEmpty()) {
            throw new NullPointerException("链表无元素!");
        }
        return head.val;
    }
    //获取队尾巴元素,获取链表中第一个节点的值
    public int lastPeek(){
        if (isEmpty()) {
            throw new NullPointerException("链表无元素!");
        }
        return last.val;
    }

    //队列的长度
    public int size() {
        return usedSize;
    }

    //队列是否为空
    public boolean isEmpty() {
        if (head == null) {
            return true;
        }
        return false;
    }

    //打印队列
    public void display() {
        Node cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
